One of the most important processes in digital signal processing is a fast Fourier transform (hereinafter called “FFT”). Also, for example, frequency domain equalization (FDE) is a technique to compensate for waveform distortion which may be caused during signal transmission in wireless or wired communications. At the frequency domain equalization (FDE), first, time-domain signal data is converted into frequency-domain data by a fast Fourier transform, next, filtering is carried out for equalization. Then, the filtered data undergoes an inverse fast Fourier transform (inverse FFT; hereinafter called “IFFT”) to be reconverted into time-domain signal data, resulting in compensating for waveform distortion in the original time-domain signals. Unless either FFT or IFFT is distinctively referred to, both are hereinafter denoted as “FFT/IFFT”.
Generally, the FFT/IFFT processing involves a “butterfly computation”. For example, an FFT device involving a butterfly computation is described in PTL 1. In the PTL 1, a “twiddle multiplication”, described below, which is a multiplication by a twiddle factor, is also described.
For example, the Cooley-Tukey butterfly computation is described in NPL 1 as an efficient FFT/IFFT processing method. However, the Cooley-Tukey FFT/IFFT uses a large number of points and thus requires a complex circuit. Hence, the FFT/IFFT processing is performed by decomposing into two smaller FFTs/IFFTs based on, for example, the Prime Factor method described in NPL 2.
FIG. 8 shows a data flow diagram 500 illustrating a 64-point FFT decomposed into two-stage radix-8 butterfly processes by utilizing, for example, the Prime Factor method. The data flow 500 includes a data sorting process 501, radix-8 butterfly computation processes consisting of butterfly computation processes 502 and 503 performed sixteen times in total, and a twiddle multiplication process 504.
With reference to the data flow shown in FIG. 8, the inputted time-domain data x(n) (where n=0, 1, . . . , 63) is Fourier-transformed into frequency-domain signals X(k) (where k=0, 1, . . . , 63) through FFT processing. Note that the data flow illustration in FIG. 8 is partly omitted. Also note that a data flow structure for IFFT processing is basically the same as shown in FIG. 8.
For a large number of FFT points, huge circuity will be required to implement the whole data flow in FIG. 8 in circuits. Thus, a typical method employed for a large number of FFT points is to implement the whole FFT process by repetitively using a circuit that implements a part of the data flow, depending on the desired processing performance.
For example, with reference to the data flow shown in FIG. 8, if an FFT device in the form of a physical circuit is created so as to perform the FFT processing on eight pieces of data in parallel (hereinafter called “in 8-data parallel” for short), repeating the processing eight times in total can achieve the 64-point FFT processing.
The eight-time repetitive processing in sequence consists of partial data flows 505a to 505h, each of which handles eight pieces of data as described in more detail below. That is, the first process corresponding to the partial data flow 505a is performed, followed by the second process corresponding to the partial data flow 505b, followed by the third process corresponding to the partial data flow 505c (not shown). Similarly, subsequent individual processes are performed in sequence up to the eighth one corresponding to the partial data flow 505h. These processes achieve the 64-point FFT processing.
In a butterfly computation, pieces of data arranged in a sequential order are read and processed in an order pursuant to a predetermined rule. Hence, a butterfly computation requires rearrangement of data, for which purpose random access memory (RAM) is used. For example, PTL 2 describes an FFT device which uses RAM for data rearrangement during a butterfly computation.
In addition, PTL 3 for example, describes a speed-enhancing technique through parallel processing of a butterfly computation on an FFT computation device which consumes less memory amount.
Incidentally, it is assumed in FFTs that a dataset identical to sequential pieces of input data, that is a range of input signals cut out for processing (hereinafter called a “process block”), cyclically occurs. However, an actual input signal is not always a periodic signal, which poses the problem of computational distortion occurring around both ends of a process block after FFT processing.
Techniques to solve this problem may include, for example, the “overlap method”. According to the overlap method, an FFT is performed on input signals arranged so as to overlap adjacent process blocks each other by a predetermined number of data pieces. Then, the post-FFT data is filtered and reconverted into time-domain signals through an IFFT, and finally only the signal data at both ends of a process block where computational distortion has occurred is removed.
The overlap method is applied to FDE (see PTL 4 and 5, for example). The following describes the overlap FDE method. FIG. 9 is a block diagram illustrating an example configuration of a digital filter circuit 700 according to the overlap FDE method. The digital filter circuit 700 is a frequency-domain filter circuit where filtering is carried out in the frequency domain. Specifically, time-domain signals are inputted as input data, transformed into frequency-domain data through an FFT, and then filtered. Subsequently, the filtered signals are re-transformed into time-domain signals through an IFFT and then outputted as output signals.
The digital filter circuit 700 includes an overlap addition circuit 710, an FFT circuit 711, a filter computation circuit 712, an IFFT circuit 713, and an overlap removal circuit 714.
The overlap addition circuit 710 sequentially generates blocks each of which is composed of N pieces of data (where N is a positive integer) from the input data representing time-domain input signals to output the blocks to the FFT circuit 711. During this operation, the overlap addition circuit 710 makes every two consecutive blocks overlap each other by M pieces of data (where M is a positive integer). The circuit may be configured to have a fixed predetermined number of overlapped data pieces M, or may be configured to set the number of overlapped data pieces during operations by, for example, referencing a value given by an upper-level circuit (not shown), such as a central processing unit (CPU), as the specified overlap value. Note that the overlap addition circuit 710 can be structured by a 2-port memory, for example.
The FFT circuit 711 performs an FFT on the time-domain input signals overlapping each other by M pieces of data as outputted from the overlap addition circuit 710, thereby transforming into frequency-domain signals, and then outputs the signals to the filter computation circuit 712.
The filter computation circuit 712 performs filtering on the frequency-domain signals that underwent a transform through the FFT circuit 711, and then outputs the filtered signals to the IFFT circuit 713. For example, if the digital filter circuit 700 performs equalization of signal distortion in a communication channel, the filter computation circuit 712 can be structured by a complex number multiplier.
The IFFT circuit 713 performs an IFFT on the filtered frequency-domain signals as outputted from the filter computation circuit 712, thereby re-transforming into time-domain signals, and then outputs the signals to the overlap removal circuit 714.
The overlap removal circuit 714 removes a total of M pieces of data from both ends of a block consisting of N pieces of data, which has been re-transformed into time-domain signals through the IFFT circuit 713, thereby taking out only the middle portion of a block and outputs it as output data.
Operations of the digital filter circuit 700 shown in FIG. 9 will now be described with reference to FIG. 10. FIG. 10 is a sequence diagram illustrating example operations of the digital filter circuit shown in FIG. 9. Process steps (1) to (5) in the following description correspond to process steps (1) to (5) in FIG. 10, respectively.
(1) Overlap Addition Processing
The overlap addition circuit 710 sequentially generates blocks each of which is composed of N pieces of data (where N is a positive integer) from the input data representing time-domain input signals. During this operation, the overlap addition circuit 710 makes every two consecutive blocks overlap each other by M pieces of data (where M is a positive integer).
Assume that input data is represented by:x[i](i=0,1, . . . )then a block consisting of N pieces of data is represented by:x[j](j=m(N−M)−N˜m(N−M)−1), where m is a positive integer)
where N represents the FFT block size and M represents the overlap value.
(2) FFT Processing
The FFT circuit 711 performs an FFT on a block consisting of time-domain signals to transform the block into a block consisting of frequency-domain signal data.
Again assume that a block consisting of N pieces of time-domain signal data is represented by:x[n](n=0,1, . . . ,N−1)then a frequency-domain block that underwent the FFT is given by:X[k](k=0,1, . . . ,N−1).(3) Frequency Domain Filtering
The filter computation circuit 712 performs filtering on each set of frequency-domain signal data consisting of a block that underwent the FFT.
A block that underwent filtering on a pre-filtering block X[k] is give by:X′[k]=H(k)·X[k](k=0,1, . . . ,N−1)
where H(k) represents a filter factor.
(4) IFFT Processing
The IFFT circuit 713 performs an IFFT on a block consisting of frequency-domain filtered signals to re-transform the block into a block consisting of time-domain signal data.
A block that underwent an IFFT performed on a pre-IFFT block X′[k] is given by:y[n](n=0,1, . . . ,N−1).(5) Overlap Removal Processing
The overlap removal circuit 714 removes M/2 pieces of overlapped data at each of the head and the end of a block y[n] that consists of N pieces of post-IFFT signal data to take out the remaining middle portion.
Consequently, a sequence of (N−M) pieces of signal data which has overlaps removed and is represented by:y′[j](j=M/2˜(N−1)−M/2)is generated.
Regarding specific processing, some digital filter circuits handle the overlapping using a general filtering process that is not necessarily limited to FDE or the like (see PTL 6, for example). The digital filter circuit disclosed in PTL 6 also performs overlap addition, FFT, frequency-domain filtering, IFFT, and overlap removal.
Meanwhile, an amount of overlap required for a filter used for the overlapping process is determined based on the impulse response length of the performed filtering. In addition, for an FFT process, a process block needs to be larger than the required amount of overlap. Accordingly, the size of a process block for an FFT is determined based on the impulse response length of the filtering.
Some techniques can reduce an amount of hardware in an apparatus used for performing FFTs on blocks of varying size (see PTL 7, for example). The orthogonal transform processor according to PTL 7 is adapted to the length of an FFT vector (which is equivalent to a “process block”) to size the memory accordingly, disable unnecessary circuit blocks, or time-share the operating hardware.